package common.advanced;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author ：Sei
 * @date ：Created in 2020/1/4 23:35
 * @description：树状数组
 * @modified By：
 * @version: $
 */
public class BinaryIndexedTree<T> {

    private int size;

    private Object[] tree;

    private final BinaryIndexedTreeStrategy<T> strategy;

    public interface BinaryIndexedTreeStrategy<T>{
        /**
         * 策略模式的单点更新策略
         * @param value
         * @param tree
         * @param index
         */
        void updateOperation(T value, Object[] tree, int index);

        /**
         * 策略模式的单点查询策略
         * @param res
         * @param tree
         * @param index
         */
        T queryOperation(T res, Object[] tree, int index);

        /**
         * 区间查询的策略
         * @param left
         * @param right
         * @return
         */
        T intervalQueryOperation(T left, T right);
    }

    public BinaryIndexedTree(BinaryIndexedTreeStrategy<T> strategy){
        this.strategy = strategy;
    }

    //region 创建方法

    /**
     * 注入更新和查询的策略
     * @param strategy
     * @param <T>
     * @return
     */
    public static <T> BinaryIndexedTree<T> on(BinaryIndexedTreeStrategy<T> strategy){
        return new BinaryIndexedTree<>(strategy);
    }

    /**
     * 创建实例
     * @param objects
     * @return
     */
    public BinaryIndexedTree<T> create(Object[] objects){
        this.size = objects.length;
        tree = Arrays.copyOf(objects, this.size);
        return this;
    }

    /**
     * 创建实例
     * @param lst
     * @return
     */
    public BinaryIndexedTree<T> create(List<T> lst){
        this.size = lst.size();
        tree = new Object[this.size+1];
        for (int i = 1; i < size+1; i++) {
            this.update(i, lst.get(i-1));
        }
        return this;
    }

    /**
     * 创建实例
     * @return
     */
    public BinaryIndexedTree<T> create(int size){
        this.size = size;
        tree = new Object[this.size+1];
        return this;
    }
    //endregion

    //region 操作方法

    /**
     *
     * @param index
     * @param value
     * @param end
     */
    public BinaryIndexedTree<T> update(int index, T value, int end){
        for(;index<=end;index+=lowbit(index)){
            this.strategy.updateOperation(value, tree, index);
        }
        return this;
    }

    /**
     *
     * @param index
     * @param value
     * @return
     */
    public BinaryIndexedTree<T>  update(int index, T value){
        return update(index, value, size);
    }

    /**
     *
     * @param index
     * @param initValue
     * @return
     */
    public T query(int index, T initValue){
        T res = initValue;
        for (;index > 0; index-=lowbit(index)) {
            res = this.strategy.queryOperation(res, tree, index);
        }
        return res;
    }

    /**
     *
     * @param left
     * @param right
     * @param initValue
     * @return
     */
    public T query(int left, int right, T initValue){
        return this.strategy.intervalQueryOperation(
                this.query(left-1, initValue),
                this.query(right, initValue)
        );
    }
    //endregion

    //region 静态方法

    /**
     * lowbit操作，非负整数二进制下最低位的1与后面的0组成的数值，如lowbit(101100)=(100)b=4
     * @param n
     * @return
     */
    private static int lowbit(int n){
        return n & (~n+1);
    }
    //endregion

    public static void main(String[] args) {
        Long[] arr = new Long[]{1L,2L,3L,4L,5L,6L,7L,8L};
        List<Long> lst = new ArrayList<>();
        Collections.addAll(lst, arr);
        BinaryIndexedTree<Long> bt = BinaryIndexedTree
                .on(new BinaryIndexedTreeStrategy<Long>() {
                    @Override
                    public void updateOperation(Long value, Object[] tree, int index) {
                        if (tree[index] == null) {
                            tree[index] = 0L;
                        }
                        tree[index] = value + (long)tree[index];
                    }

                    @Override
                    public Long queryOperation(Long res, Object[] tree, int index) {
                        if (tree[index] == null) {
                            tree[index] = 0L;
                        }
                        res += (long) tree[index];
                        return res;
                    }

                    @Override
                    public Long intervalQueryOperation(Long left, Long right) {
                        return right - left;
                    }
                }).create(8)
                .update(5, 6L)
                .update(4, -3L);

        System.out.println(bt.query(8, 0L));
        System.out.println(bt.query(2, 6, 0L));
    }
}
